package algorithm.middle;

/**
 * @author 江岸
 * @version V1.0
 * @ClassName: CharacterReplacement424
 * @description:给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。
 *
 * 注意：字符串长度 和 k 不会超过 104。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-repeating-character-replacement
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2021/2/217:52
 * @since V1.0
 */
public class CharacterReplacement424 {
    //双指针，滑动窗口
    public int characterReplacement(String s, int k) {
        char[] arr = s.toCharArray();
        int[] num = new int[26];
        int max = 0;
        int res = 0;
        //滑块的左右边界
        int left = 0;
        int right = 0;
        while(right<arr.length){
            //往右边读取一个字符
            num[arr[right]-'A']++;
            max = Math.max(max,num[arr[right]-'A']);
            //如果滑块的数目大于保存的最大字符数+可替代数，说明滑块需要向右话滑动
            right++;
            if (right-left>max+k){
                // 说明此时 k 不够用
                // 把其它不是最多出现的字符替换以后，都不能填满这个滑动的窗口，这个时候须要考虑左边界向右移动
                // 移出滑动窗口的时候，频数数组须要相应地做减法
                num[arr[left]-'A']--;
                left++;
            }
            res = Math.max(res, right - left);
        }
        return res;

    }

}
